package io.github.handyang.algorithms.sort;

import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;

@Slf4j
public class MSDRadixSortAlgorithms implements SortAlgorithms {

    @Override
    public void sort(int[] arr) {
        int max = arr[0];
        for (int i : arr) {
            max = Math.max(i, max);
        }

        int radix = 1;
        while (max / radix >= 10) {
            radix *= 10;
        }

        sort(arr, new int[arr.length], 0, arr.length - 1, radix);
    }

    private void sort(int[] arr, int[] helper, int lo, int hi, int radix) {
        if (lo >= hi || radix == 0) return;

        log.debug("\narr:{},lo:{},hi:{},radix:{}", Arrays.toString(arr), lo, hi, radix);

        int[] count = new int[12];
        for (int i = lo; i <= hi; i++) {
            count[(arr[i] / radix) % 10 + 2]++;
        }
        log.debug("count:{}", Arrays.toString(count));

        //count转index
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        log.debug("count index:{}", Arrays.toString(count));
        for (int i = lo; i <= hi; i++) {
            helper[lo + count[(arr[i] / radix) % 10 + 1]++] = arr[i];
        }

        log.debug("count after:{}", Arrays.toString(count));

        if (hi + 1 - lo >= 0) System.arraycopy(helper, lo, arr, lo, hi + 1 - lo);

        log.debug("sort result:{}\n", Arrays.toString(arr));

        for (int i = 0; i < 10; i++) {
            sort(arr, helper, lo + count[i], lo + count[i + 1] - 1, radix / 10);
        }
    }
}
